package com.leetcode.partition4;

import java.util.ArrayList;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/10/27 8:31
 */
public class LC301删除无效的括号 {

    public static List<String> removeInvalidParentheses(String s) {
        List<String> answer = new ArrayList<>();
        //最少需要删除的左括号和右括号数量
        int leftRemove = 0, rightRemove = 0;
        for (int i = 0; i < s.length(); i++) {
            //如果是左括号直接添加，如果是右括号；查看是否有左括号，如果有，则减少一个左括号，否则需要删除右括号，也就是rightRemove++
            if (s.charAt(i) == '(') {
                leftRemove++;
            } else if (s.charAt(i) == ')' && leftRemove > 0) {
                leftRemove--;
            } else if (s.charAt(i) == ')') {
                rightRemove++;
            }
        }
        backtracking(answer, s, 0, 0, 0, leftRemove, rightRemove);
        if (answer.size() == 0) answer.add("");
        return answer;
    }

    public static void main(String[] args) {
//        String s = "()())()";       //()()()、(())()
        String s = ")(()c))(";
//        String s = ")(";
//        String s = "(()";
        System.out.println(removeInvalidParentheses(s));
    }

    private static void backtracking(List<String> answer, String s, int startIndex, int leftParentheses, int rightParentheses
            , int leftRemove, int rightRemove) {
        //如果需要删除的括号都删除完了，该字符串也是个合法字符串，就加入结果中
        if (leftRemove == rightRemove && leftRemove == 0) {
            if (isValid(s)) answer.add(s);
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            //去重，如果有两个都是左括号或者都是右括号，没有必要进行判断
            if (i > startIndex && s.charAt(i) == s.charAt(i - 1)) {
                if (s.charAt(i) == '(') leftParentheses++;
                else if (s.charAt(i) == ')') rightParentheses++;
                continue;
            }
            //字符串的长度不够删除，进行剪枝
            if (leftRemove + rightRemove > s.length() - 1) return;

            String nextString = s.substring(0, i) + s.substring(i + 1);
            if (s.charAt(i) == '(' && leftRemove > 0) {
                backtracking(answer, nextString, i, leftParentheses, rightParentheses, leftRemove - 1, rightRemove);
            }
            if (s.charAt(i) == ')' && rightRemove > 0) {
                backtracking(answer, nextString, i, leftParentheses, rightParentheses, leftRemove, rightRemove - 1);
            }
            if (s.charAt(i) == '(') {
                leftParentheses++;
            } else if (s.charAt(i) == ')') {
                rightParentheses++;
            }
            //右括号数量始终不能大于左括号数
            if (rightParentheses > leftParentheses) break;
        }
    }

    private static boolean isValid(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                count++;
            } else if (s.charAt(i) == ')') {
                count--;
                if (count < 0) return false;
            }
        }
        return count == 0;
    }
}
